import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.reverseWords("the sky is blue"));
        System.out.println(s.reverseWords("  hello world  "));
        System.out.println(s.reverseWords("a good   example"));

    }
}


//反转，再反转单词
class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();

        //去除多余空格
        int start = 0, end = s.length() - 1;
        while (start <= end && s.charAt(start) == ' ') {
            start++;
        }
        while (start <= end && s.charAt(end) == ' ') {
            end--;
        }
        for (int i = start; i <= end; i++) {
            char c = s.charAt(i);
            if (c == ' ' && sb.charAt(sb.length() - 1) == ' ') {
                continue;
            }
            sb.append(c);
        }

        //reverse whole String
        reverseSubString(sb, 0, sb.length() - 1);

        //reverse words
        int left = 0, right = 0;
        while (right < sb.length()) {
            if (sb.charAt(right) == ' ') {
                reverseSubString(sb, left, right - 1);
                left = right + 1;
            }
            right++;
        }
        reverseSubString(sb, left, right - 1);

        return sb.toString();
    }

    public void reverseSubString(StringBuilder sb, int l, int h) {
        for (int i = l, j = h; i < j; i++, j--) {
            char temp = sb.charAt(i);
            sb.setCharAt(i, sb.charAt(j));
            sb.setCharAt(j, temp);
        }
    }
}


//调用库函数
class Solution1 {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        List<String> list = Arrays.asList(words);
        Collections.reverse(list);
        return String.join(" ", list);
    }
}
